How does the system implement recursion?

	stack of activation records


What's stored in an Activation Record?

	space for parameters and local variables


Why is a stack a good fit for this problem?

	methods return in reverse order of calls


What happens to the stack when a method is called?

	push activation record on method call


What happens to the stack when a method returns?

	pop activation record when method completes


Give the stack contents for recursive binary search.

a:  4  7 13 19 25 27 41 52 57 63
x: 52

    int binarySearch( Comparable[] a, Comparable x,
                       int low, int high ) {
        if( low > high )
            return NOT_FOUND;

        int mid = ( low + high ) / 2;

        if( a[ mid ].compareTo( x ) < 0 )
            return binarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compareTo( x ) > 0 )
            return binarySearch( a, x, low, mid - 1 );
        else
            return mid;
    }



Suppose you need to compute the nth Fibonacci number.
What are the Fibonacci numbers?

	1 1 2 3 5 8 13 21 34 55 89
	next number is sum of previous two numbers
	The number of rabbits after n months.


How do you get the nth number based on previous numbers?

	fib(n) = fib(n-1) + fib(n-2)


What's the base case?

	fib(1) = 1


With only one base case, what happens when you try to compute fib(2)?
How do you solve this problem?

	fib(2) = fib(1) + fib(0)
	add a second base case
	fib(2) = 1


How do you put this all together into a recursive method?

	int fib (int n) {
	    if (n <= 2)
	        return 1;
	    else
	        return fib(n-1) + fib(n-2);
	}


DEMO	(Fib1.java)


How long does it take to compute the 30th Fibonacci Number?


How long does it take to compute the 40th Fibonacci Number?


How many adds are needed to get the 40th Fibonacci Number?


DEMO	(Fib2.java)


Why does the recursive method take so long?

	redundant computation
	fib(n) computes fib(n-1) and fib(n-2)
	fib(n-1) computes fib(n-2) again
	running time is exponential


What's the fourth Rule of Recursion?

	4. never solve the same problem instance more than once